

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
        vector<int> ans;
        deque<int> q; //双端队列做单调队列
        
        for(int i=0;i<nums.size();i++)
        {
            //入队列
            while(!q.empty()&&nums[q.back()]<=nums[i]){
            q.pop_back(); //队列不为空且队尾元素小于等于
            }
            q.push_back(i);

            //出
            if(i-q.front()>=k)
            {
                q.pop_front();
            }

            //记录
            if(i>=k-1)
            {
                ans.push_back(nums[q.front()]);
            }

        }
        return ans;
    }
};